package com.skh.array;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 找到所有数组中消失的数字
 * created by skh on 2018/8/20
 */
public class FindAllNumbersDisappearedInAnArray {

	/*

	给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

	找到所有在 [1, n] 范围之间没有出现在数组中的数字。

	您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

	示例:

	输入:
	[4,3,2,7,8,2,3,1]

	输出:
	[5,6]

	 */


	/*
	利用set的唯一性
	 */
	public List<Integer> findDisappearedNumbers(int[] nums) {

		int n = nums.length;

		Set set = new HashSet();
		for (int num : nums) {
			set.add(num);
		}

		List<Integer> rs = new ArrayList<>();

		for (int i=1;i<=n;i++) {
			boolean contains = set.contains(i);
			if (!contains) {
				rs.add(i);
			}
		}

		return rs;

	}


	/**
	 * 方法二：原地修改
	 * 我们需要知道数组中存在的数字，由于数组的元素取值范围是 [1, N]，所以我们可以不使用额外的空间去解决它。
	 * 我们可以在输入数组本身以某种方式标记已访问过的数字，然后再找到缺失的数字。
	 * 算法：
	 *
	 * 遍历输入数组的每个元素一次。
	 * 我们将把 |nums[i]|-1 索引位置的元素标记为负数。即 nums[|nums[i]|- 1]×−1 。
	 * 然后遍历数组，若当前数组元素 nums[i] 为负数，说明我们在数组中存在数字 i+1。
	 * 可以通过以下图片示例来帮助理解。
	 */

	public List<Integer> findDisappearedNumbers2(int[] nums) {
		////第一遍扫描，根据数组的值找到对应的下标，比如3对应下标2,将arr[2]设置成负数
		for (int i = 0; i < nums.length; i++) {
			int newIndex = Math.abs(nums[i])-1;

			if (nums[newIndex] > 0) {
				nums[newIndex] *= -1;
			}
		}



		List<Integer> rs = new ArrayList<>();
		//第二遍扫描，找到所有非负数，非负数所在的下标+1，即为缺失的数字
		for (int i = 1; i <=nums.length ; i++) {
			if (nums[i - 1] > 0) {
				rs.add(i);
			}
		}

		return rs;

	}


}
